package com.mc.linkerlist;

/**
 * @Description: 单链表
 * @Author: MoChen
 */
public class HLinkerList {

    // 链表的头结点
    HNode head = null;

    // 初始化一个空链表
    boolean InitList(HLinkerList L){
        L.head = new HNode(); // 分配一个头结点,如果不带头结点此处直接赋空
        L.head.next = null; // 头结点之后暂时没有结点
        return true;
    }

    // 在第i个位置插入元素e
    boolean ListInsert(HLinkerList L, int i, int e) {
        if(i < 1) {
            return false;
        }
        // 以下代码段为不带头结点的操作
//        if(i == 1) { // 插入第一个结点的操作与其他结点操作不同
//            HNode s = new HNode();
//            s.data = e;
//            s.next = L.head.next;
//            L.head = s; // 头指针指向新结点
//        }
//        HNode p; // 指针p向前扫描到的结点
//        int j = 0; // 当前p指向的是第几个结点，不带的话此处赋1
//        p = L.head; // L指向头结点，头结点是第0个结点
//        while (p != null && j < i - 1) { // 循环找到 i - 1 个结点
//            p = p.next;
//            j++;
//        }
        HNode p = GetElem(L, i - 1);

//        if(p == null){ // i值不合法
//            return false;
//        }
//        HNode s = new HNode();
//        s.data = e;
//        s.next = p.next;
//        p.next = s; // 将结点s连到p之后
//        return true; // 插入成功

        return InsertNextNode(p, e);
    }

    // 后插操作：在p结点之后插入元素e
    boolean InsertNextNode(HNode p, int e){
        if(p == null){
            return false;
        }
        HNode s = new HNode();
        s.data = e; // 新结点s存储数据e
        s.next = p.next;
        p.next = s; // 新结点s挂到p身上
        return true;
    }

    // 前插操作：在p结点之前插入元素e
    boolean InsertPriorNode(HNode p, int e){
        if(p == null){
            return false;
        }
        HNode s = new HNode();
        s.next = p.next;
        p.next = s; // 新结点s挂到p身上
        s.data = p.data; // 将p里面的元素复制到s中
        p.data = e; // p中的元素覆盖为e
        return true;
    }

    // 按位序删除
    boolean ListDelete(HLinkerList L, int i, int e){
        if(i < 1){
            return false;
        }
//        HNode p; // 指针p向前扫描到的结点
//        int j = 0; // 当前p指向的是第几个结点，不带的话此处赋1
//        p = L.head; // L指向头结点，头结点是第0个结点
//        while (p != null && j < i - 1) { // 循环找到 i - 1 个结点
//            p = p.next;
//            j++;
//        }
        HNode p = GetElem(L, i - 1);

        if(p == null){ // i值不合法
            return false;
        }
        if(p.next == null){ // 第i - 1个结点后面已无其他结点
            return false;
        }
//        HNode q = p.next; // 令q指向被删除的结点
//        e = q.data; // 用e返回元素的值
//        p.next = q.next; // 将q结点从链中断开
//        return true; // 删除成功

        return DeleteNode(p);
    }

    // 删除指定结点p
    boolean DeleteNode(HNode p){
        if(p == null){
            return false;
        }
        HNode q = p.next; // 令q指向p的后继结点
        p.data = p.next.data; // 和后继结点交换数据域
        p.next = q.next; // 将q结点从链中断开
        return true;
    }

    // 按位查找，返回第i个元素
    HNode GetElem(HLinkerList L, int i){
        if(i < 0){
            return null;
        }
        HNode p; // 指针p向前扫描到的结点
        int j = 0; // 当前p指向的是第几个结点，不带的话此处赋1
        p = L.head; // L指向头结点，头结点是第0个结点
        while (p != null && j < i) { // 循环找到 i 个结点
            p = p.next;
            j++;
        }
        return p;
    }

    // 按值查找
    HNode LocateElem(HLinkerList L, int e){
        HNode p = L.head.next;
        // 从第一个结点开始查找数据域为e的结点
        while(p != null && p.data != e){
            p = p.next;
        }
        return p; // 找到后返回该结点，否则返回null
    }

    // 求表的长度
    int Length(HLinkerList L){
        int len = 0;
        HNode p = L.head;
        while(p.next != null){
            p = p.next;
            System.out.println("链表第" + len + "个数据:" + p.data);
            len++;
        }
        return len;
    }
}
